import java.util.Stack;

public class Solution {
//    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//    有效字符串需满足：
//    左括号必须用相同类型的右括号闭合。
//    左括号必须以正确的顺序闭合。
//    每个右括号都有一个对应的相同类型的左括号。每个右括号都有一个对应的相同类型的左括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch1=s.charAt(i);
            if(ch1=='('||ch1=='{'||ch1=='['){
                stack.push(ch1);
            }else{
                if(stack.empty()){
                    return false;
                }else {
                    char ch2=stack.peek();
                    if(ch2=='('&&ch1==')'||ch2=='{'&&ch1=='}'||ch2=='['&&ch1==']'){
                        stack.pop();
                    }else {
                        return false;
                    }
                }

            }

        }
        return stack.empty();
    }
}
